\subsubsection{Solución elegida}

El algoritmo diseñado devuelve la secuencia de jugadas que se produjeron en cada turno, de forma tal que cada jugador al momento de retirar cartas lo hizo de manera óptima. 
Aquí lo que se considera como óptimo en cada turno es retirar desde alguno de los costados la secuencia de cartas, de 1 o más, que
al momento de finalizar me garantice la mejor diferencia de puntos a mi favor. \\

Puede suceder que en determinados turnos la suma de puntos que se obtenga sea menor que 0 ó más aun, que me haga tener menos puntos que el adversario luego de mi jugada. Pero el objetivo es ganar el juego con la mejor diferencia de puntos a mi favor, y lo que resultará óptimo entonces
sera la jugada que me permita hacerla mejor diferencia en el global del juego y no en un turno dado.  \\

Hay cartas para determinados juegos que hacen imposible ganarlos, en estos casos se reducirá el 
score por el que se pierde. Por Ejemplo la secuencia [ -1,-2,-1 ] siempre hará que pierda el jugador que comienza la partida. Si retira  -1, el otro retirará el otro -1 dejando el -2 para finalizar el juego, que se pierde por -3 a -1, pero si retiran dos cartas [ -1 ,-2 ] o [ -2 , -1 ], también pierde por -3 a -1. \\ 

Para poder resolver el ejercicio se decidió una implementación de tipo divide \& conquer en un primer intento para luego adaptar esto hacia programación dinámica. 
El algoritmo recorre cada una de las subsecuencias posibles de izquierda a derecha y de derecha a izquierda y se llama recursivamente con el otro jugador en el turno actual. 
Esto hace que para cada subsecuencia se vea que resultado tendriá en el mejor caso si se sacara esa subsecuencia y se la sumara a 
los puntos obtenidos en los subjuegos de los siguientes turnos. \\

Para cada subsecuencia, dadas las cartas sobre la mesa, retiro esas cartas y hago que juegue el otro jugador. Como este juega de manera óptima al igual que yo, la jugada siguiente arrojará un resultado. Si a ese resultado que se obtiene con la secuencia restante le sumo los puntos que retiré, puedo tener idea 
de cuanta diferencia de puntos sacaría al otro jugador si mi jugada en este turno fuera retirar esa secuencia que probe. \\
Al hacer esta prueba en cada subsecuencia, de derecha a izquierda y de izquierda a derecha puedo estar seguro que la jugada que realicé es la que me da el mejor beneficio en las jugadas subsiguientes y en el resultado final. \\
El coeficiente que trato de maximizar para cada subsecuencia es: 
(\emph{  puntos retirados + diferencia en el subjuego} ) la subsecuencia que maximice este valor sera la candidata a jugada en el turno dado.\\

Este tipo de implementación si no contará con una parte de programación dinámica es claro que repetiría muchísimos resultados intermedios que son
descartados. En una secuencia de N números, las subsecuencias de longitud 1 que se pueden generar en base a la secuencia original, forman juegos que serían calculados infinidad de veces si no se utiliza un mecanismo para reutilización de resultados.\\

Como el manejo de las extracciones en la  secuencia original se hace a partir de mover hacia el centro 2 punteros al comienzo y fin de la subsecuencia que se está analizando, se utilizaron estos indicadores como identificador de un juego para el guardado del resultado. Cada vez que extraigo a izquierda se incrementa un valor \emph{start}, y cada vez que se extrae a derecha se decrementa un valor \emph{end}. El resultado de ese juego será guardado en una matriz donde el valor en las filas es el valor de \emph{start} y en valor en las columnas es el valor de \emph{end}. 
Así el valor de la subsecuencia que comienza en la posición 0 y termina en la posición 2 tendrá la coordenada [0][2].
En esa posición de la matriz se guardará ese sub resultado.
Con esta matriz se reducirá la complejidad del algoritmo.




% Por ejemplo, dada la secuencia [ -3 -2 -1 2 1 0 -2 -5 -2 ]
% mi primera extraccion sera -3 -2 -1 2 1 0 que sumara -3
% y si bien ahora tengo -3 y el otro 0 
% en el global me favorece, como se ve a continuacion. \\
% El otro debe elegir ahora entre [ -2 -5 -2 ]  y obviamente eligira retirar -2
% dado que es lo mejor que puede hacer. Si 
% retira -5 -2 ya perdio, entonces tomara un -2. Luego 
% debo elegir entre [ -5 -2 ] y dejare el [ -5 ] para el fin de la partida.
% Esto arrojara un resultado final de -5 a -7, +2 para mi en el global, mis extracciones fueron  [ -3 -2 -1 2 1 0 ] [-2] 
% y las de el otro jugador [ -2 ] [ -5 ].\\
% Si yo hubiera retirado cualquier otra subsecuencia en el paso 1 hubiera
% obtenido menos puntos de diferencia con el otro.
% \\
% \\
% Otro ejemplo,dada la secuencia [ -3, -2, -1, 2, 0, -1, -4, -2 ]  se vera que lo mejor que puedo hacer es reducir
% el margen de diferencia que me sacara el otro jugador. Pero si yo comienzo, no hay forma e no perder la partida.\\
% \\
% Caso 1:
% Retiro [ -2 ] dejando -3, -2, -1, 2, 0, -1, -4. Ok el otro jugador tomara [ -3, -2, -1, 2, 0, -1 ]  que suma -5 sabiendo
% que me obliga a tomar el -4,  que me lleva al -6 y me hace perder la partida.\\
% \\
% Caso 2:
% Como se que esa secuencia jugara el otro jugador si saco el -2 trato por ahi yo primero,
% entonces retiro [ -3, -2, -1, 2, 0, -1 ] , sumo -5 y dejo [ -1 -4 -2 ]. \\ Estamos 
% en problemas de nuevo, por que el otro jugador sabiendo que yo ya cuento
% con -5 puntos puede permitirse sumar hasta -5 puntos si me deja puntos para restar a mi. 
% El otro jugador tomara [ -1 -4 ] y me dejara el [ -2 ] para que yo lo tome 
% con lo que me gana nuevamente. 
% \\
% Se podrian seguir probando combinaciones pero esta secuencia 
% siempre hara que el que comienza pierda.\\
% \\
% Por ej: si tomo el -3 solo y dejo [ -2, -1, 2, 0, -1, -4, -2]
% el otro jugador seguramente tomara [ -2, -1, 2, 0 ] quedandose con -1 
% punto y aparte la posibilidad de definir el partido. Dado que 
% con esas cartas [-1 -4 -2] lo unico que me queda hacer es tomar el -1 
% para luego tener que en el otro turno tomar el [-4] por que el -2 sera
% tomado por mi adversario.



\subsubsection{Demostración}

\\
\\
Jugar es la función que implementa el algoritmo, Juego un objeto que mantiene el estado del juego actual
y matriz es la matriz de resultados parciales\\
\begin{pseudocode}
{Jugar}{Juego,Matriz}
	\\
	\IF Matiz[Juego.start][Juego.end] \\
	\THEN
	\BEGIN
		\RETURN{Matiz[Juego.start][Juego.end]}\\
	\END\\

	\\
	maxDiff \GETS MIN\_INT\\
	maxJuego \GETS NULL\\
	\\
	\FOR i  \GETS 1 \TO Juego.cantidadDeNumeros -1 \DO
		\BEGIN
			\\
			sumIzq \GETS \CALL{Sumar}{1,i,izq} \\
			sumDer \GETS \CALL{Sumar}{Juego.cantidadDeNumeros-1,-i,der}
			\\
			\\
			JuegoIzq \GETS \CALL{Extraer}{1,i,Juego}\\
			JuegoDer \GETS \CALL{Extraer}{Juego.cantidadDeNumeros-1,-i,Juego}\\
			\\
			JuegoDer.pasarTurno()\\
			JuegoIzq.pasarTurno()\\
			\\
			Juego(JuegoIzq)\\
			Juego(JuegoDer)\\
			\\
			\IF JuegoIzq.scoreMio + sumIzq - JuegoIzq.scoreDelOtro  \textgreater maxDiff\\
			\THEN
			\BEGIN
				maxDiff \GETS JuegoIzq.scoreMio + sumIzq - JuegoIzq.scoreDelOtro\\
				JuegoIzq.scoreMio \GETS  JuegoIzq.scoreMio + sumIzq\\
				maxJuego \GETS JuegoIzq\\
			\END			
			\\
			\\
			\IF JuegoDer.scoreMio + sumDer - JuegoDer.scoreDelOtro  \textgreater maxDiff \\
			\THEN
			\BEGIN
				maxDiff \GETS JuegoDer.scoreMio + sumDer - JuegoDer.scoreDelOtro \\
				JuegoDer.scoreMio \GETS  JuegoDer.scoreMio + sumDer\\
				maxJuego \GETS JuegoDer	\\	
			\END				
		\END\\
		\\
	Matiz[Juego.start][Juego.end] \GETS MaxJuego\\
	\\
	\RETURN{Matiz[Juego.start][Juego.end]}

\end{pseudocode}

El algoritmo trata  de ver todas las formas en las que se pueden retirar números desde ambos lados. Para cada una de estas extracciones o jugadas posibles deja jugar al otro jugador y ve si esa jugada le conviene(llamada recursiva Juego(JuegoIzq) y cálculo de máximo). \\

Acá es donde alguien puede objetar que si retiro \emph{i} números de \emph{n} y doy los \emph{n-i} números para que el otro juegue el algoritmo tiene una falla grave dado que no puedo saber todos los juegos posibles que hace el otro jugador con esa secuencia restante. Y por lo tanto el valor que tomo como referencia a ver si es un máximo\emph{(mi extracción + diferencia en sub juego)}, no es correcto dado que no estoy cubriendo todas las posibilidades de juego del otro jugador. Luego el juego que estoy tomando no es máximo. \\

El otro jugador está jugando con el mismo algoritmo en su turno, con los números que dispone. 
Eso hará que trate de maximizar los puntos a su favor. De esta manera el otro jugador va a jugar de manera óptima. Pero de  nuevo el otro jugador dependerá de mis jugadas en el paso siguiente. 
Como cada sub llamada esta realizada al mismo algoritmo, pero con diferente jugador en cada caso, la decisión que se toma es en base a la mejor jugada que pueda hacer el otro y de esa manera trato de hacer la mejor jugada yo.
De esta manera, es correcto tomar como referencia el valor del juego del otro jugador para yo poder tratar de maximizar mi puntaje. 
En ese punto se ve como, luego de dividir el problema en subproblemas, estos subproblemas son resueltos adecuadamente y luego combinados al sumarle los puntos de este turno.
Solo resta retornar la opción que resulto máxima entre los i que comparé. \\

También se puede ver utilizando inducción fuerte en la cantidad de fichas.
Para un juego de 1 sola ficha se puede ver claramente que solo tenemos la opción de poder retirar una ficha.
Retirar la única ficha disponible será nuestra única opción y la óptima.\\

Suponiendo que para cualquier juego de $n$ o menos fichas el algoritmo 
va a producir una secuencia de una o mas jugadas óptimas para cada uno de los turnos.
Cada uno de estos juegos posibles con las $n$ fichas son guardados en una matris. 
De esta manera para cada sub secuencia posible entre los $n$ numeros
sé como va a jugar mi algoritmo.

Ahora dado un juego con $n+1$ fichas tengo 2 posibilidades:
En el primero de los casos se suman todos los números de la secuencia.\\
En el segundo de los casos se extraen 1 o más números, se los suma y se los compara.
Para cada extraccion se ve que subjuego genera(todos estos de $n$ o menos fichas) y se elige
el que maximice la diferencia, para todas las extracciones posibles.\\
Luego al elegir el maximo entre los 2 casos estoy eligiendo el maximo entre la jugada que retira 
todas las fichas disponibles $(n+1)$ y el mejor sub juego de $n$ o menos fichas. 
De esta manera estoy seguro que el juego de $n+1$ fichas va a ser optimo.
\\
\\
Supongamos entonces que no es asi.\\ Existe una solucion $S'$ de $n+1$ fichas 
que es optima y que es mejor a la encontrada por mi algoritmo. \\

Para ese $S'$ o bien consiste en una jugada de 1 solo turno en el que se suman todos 
los numeros disponibles $n+1$, o $S'$ es un juego con mas de 1 turno jugado.

Si $S'$ consiste en un solo turno, y  $S$ es la solucion que encontro
mi algoritmo. Como mi algoritmo compara en cada juego la jugada que consiste en retirar todos 
los numeros disponibles o retirar algunos, hubiera elegido esta jugada si fuera mejor que los 
sub juegos que tenia, dado que 
comparo esta jugada contra los sub juegos optimos. Entonces $S$ es menor o 
igual a $S'$. Llegamos a una contradiccion ya que $S'$ era optimo.

Si $S'$ consiste en una secuencia de jugadas. Entonces como $S$ la solucion
que encontro mi algorimo no es mejor que $S'$ quiere decir que hay una 
jugada a partir de la cual $S'$ es mejor que $S$. Una sub jugada de $n$ o
menos fichas en $S'$ es mejor a  una sub jugada de $S$. Pero 
aca de nuevo estamos en una contradiccion pues esa sub jugada 
va a ser sobre una cantidad de fichas de $n$ o menos y por 
hipotesis las jugadas de $n$  o menos fichas con las
que cuenta mi algoritmo son optimas. 
